#include "linearList.h"
using namespace std;
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for (int i = 0; i < curNumberOfItem - 1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem - 1] << endl;
}

//初始化顺序表
sequenceList::sequenceList(const int& max, const int& L, float data[])
{
    myList = new float[max];
    maxCapcity = max;
    curNumberOfItem = L;
    for (int i = 0; i < L; i++)
        myList[i] = data[i];
}

//销毁顺序表
sequenceList::~sequenceList()
{
    delete[]myList;
    myList = NULL;
}

//添加元素顺序表尾
bool sequenceList::addItem(const float& New)
{
    if (curNumberOfItem == maxCapcity)
        return 0;
    myList[curNumberOfItem] = New;
    curNumberOfItem++;
    return 1;
}

//插入元素到index位置
bool sequenceList::insertItem(const int& index, const float& New)
{
    if (index<0 || index>curNumberOfItem || curNumberOfItem == maxCapcity)
        return 0;
    for (int i = curNumberOfItem; i > index; i--)
        myList[i] = myList[i - 1];
    myList[index] = New;
    curNumberOfItem++;
    return 1;
}

//删除元素
int sequenceList::deleteItem(const float& x)
{
    int L = this->locate(x);
    if (L < 0)return -1;
    curNumberOfItem--;
    for (int i = L; i < curNumberOfItem; i++)
        myList[i] = myList[i + 1];
    return L;
}

//查找元素（按序号找）
bool sequenceList::locate(const int& loc, float& val)
{
    if (loc < 0 || loc >= curNumberOfItem)
        return 0;
    val = myList[loc];
    return 1;
}

//查找元素（按值找）
int sequenceList::locate(const float& x)
{
    int i = 0;
    while (i < curNumberOfItem && myList[i] != x)
        i++;
    if (i < curNumberOfItem)
        return i;
    return -1;
}

//倒序排列元素
void sequenceList::reverse()
{
    int small = 0, large = curNumberOfItem - 1;
    while (small < large) {
        float data = myList[small];
        myList[small++] = myList[large];
        myList[large--] = data;
    }
}

//链表单元初始化
listNode::listNode(float nodeData, listNode* succ) {
    data = nodeData; next = succ;
}
listNode::~listNode() {}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while (curNode != lastNode)
    {
        if (curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }


        curNode = curNode->next;
    }
}

//销毁链表
linkList::~linkList()
{
    delete firstNode; firstNode = NULL;
    curNode = NULL; lastNode = NULL;
}

//初始化链表
linkList::linkList(const int& l, float num[])
{
    firstNode = new listNode;
    listSize = l;
    listNode* first = new listNode(num[0]);
    curNode = first;
    firstNode->next = curNode;
    for (int i = 1; i < l; i++)
    {
        listNode* data = new listNode(num[i]);
        curNode->next = data;
        curNode = curNode->next;
    }
    lastNode = curNode;
}

//插入元素(头插法)
bool linkList::headInsertItem(const float& x)
{
    //if (x == NULL)return 0;
    listNode* newFirst = new listNode(x);
    newFirst->next = firstNode->next;
    firstNode->next = newFirst;
    listSize++;
    return 1;
}

//插入元素(尾插法）
bool linkList::tailInsertItem(const float& x)
{
    //if (x == NULL)return 0;
    listNode* newLast = new listNode(x);
    lastNode->next = newLast;
    lastNode = newLast;
    listSize++;
    return 1;
}

//插入元素到index位置，成功返回插入位置，错误返回-1
int linkList::insertItem(const int& index, const float& x)
{
    if (index < 0 || index >= listSize)
        return -1;
    if (index == 0) {
        this->headInsertItem(x);
        return 0;
    }
    if (index == listSize - 1) {
        this->tailInsertItem(x);
        return index;
    }
    listSize++;
    int i = 0;
    curNode = firstNode;
    while (i++ < index)
        curNode = curNode->next;
    listNode* newNode = new listNode(x);
    newNode->next = curNode->next;
    curNode->next = newNode;
    return index;
}

//删除元素
int linkList::deleteItem(const float& x)
{
    int l = locate(x);
    if (l == -1)return -1;
    listSize--;
    curNode = firstNode;
    int i = 0;
    while ((i++) < l)curNode = curNode->next;
    listNode* p = curNode;
    p = p->next;
    curNode->next = p->next;
    delete p; p = NULL;
    return l;
}

//查找元素（按序号找）
bool linkList::locate(const int& index, float& val)
{
    if (index < 0 || index >= listSize)
        return 0;
    curNode = firstNode;
    for (int i = 0; i <= index; i++)
        curNode = curNode->next;
    val = curNode->data;
    return 1;
}

//查找元素（按值找）
int linkList::locate(const float& x)
{
    curNode = firstNode;
    int i = 0;
    while (i < listSize && curNode->next->data != x) {
        i++;
        curNode = curNode->next;
    }
    if (i == listSize)return -1;
    else return i;
}

//递增排序
void linkList::ascendingOrder()
{
    curNode = firstNode;
    float* Data = new float[listSize];
    int i = 0;
    while (curNode != lastNode)
    {
        Data[i++] = curNode->next->data;
        curNode = curNode->next;
    }
    for (i = 0; i < listSize - 1; i++) {
        int min = i;
        for (int j = i + 1; j < listSize; j++)
            if (Data[j] < Data[min])
                min = j;
        float d = Data[i];
        Data[i] = Data[min];
        Data[min] = d;
    }
    curNode = firstNode;
    i = 0;
    while (curNode != lastNode)
    {
        curNode->next->data = Data[i++];
        curNode = curNode->next;
    }
}

//倒序排列元素
void linkList::reverse()
{
    float* Data = new float[listSize];
    int i = listSize;
    curNode = firstNode;
    while (curNode != lastNode)
    {
        Data[--i] = curNode->next->data;
        curNode = curNode->next;
    }
    curNode = firstNode;
    i = 0;
    while (curNode != lastNode)
    {
        curNode->next->data = Data[i++];
        curNode = curNode->next;
    }
}


void merge(linkList& a, linkList& b)
{
    a.lastNode->next = b.firstNode->next;
    a.lastNode = b.lastNode;
    a.listSize += b.listSize;
    a.ascendingOrder();
    a.reverse();
}